package linkedlist;

import org.omg.PortableServer.LIFESPAN_POLICY_ID;

import javax.lang.model.type.ArrayType;
import java.util.ArrayList;
import java.util.*;

public class LinkedList1 {
    static class ListNode {
        int val;
        ListNode next;
        ListNode prev;

        public ListNode(int val) {
            this.val = val;
        }

        public ListNode() {
        }
    }

    static ListNode head;
    static ListNode last = head;

    static void addFirst (int data) {
        ListNode node = new ListNode(data);
        if (head == null) {
            head = node;
            last = node;
        } else {
            node.next = head;
            head.prev = node;
            head = node;
        }
    }

    static void addLast (int data) {
        if (last == null) {
            addFirst(data);
        } else {
            ListNode node = new ListNode(data);
            last.next = node;
            node.prev = last;
            last = node;
        }
    }

    static int size () {
        int c = 0;
        ListNode node = head;
        while (node != null) {
            node = node.next;
            c++;
        }
        return c;
    }

    static void addIndex (int data, int pos) {
        ListNode curNode = findIndex(pos);
        ListNode newNode = new ListNode(data);

        if (curNode != null) {
            if (curNode.prev == null) {    //说明curNode是头节点
                curNode.prev = newNode;
                newNode.next = curNode;
                head = newNode;
            } else {
                curNode.prev.next = newNode;
                newNode.prev = curNode.prev;
                newNode.next = curNode;
            }
        } else {
            addLast(data);
        }
    }

    private static ListNode findIndex (int index) {
        if (index < 0 || index > size()) {
            throw new ArrayIndexOutOfBoundsException();
        }
        ListNode curNode = head;
        while (curNode != null && index != 0) {
            curNode = curNode.next;
            index--;
        }
        return curNode;
    }

    static void display (ListNode head) {
        ListNode tmpNode = head;
        while (tmpNode != null) {
            System.out.print(tmpNode.val + " ");
            tmpNode = tmpNode.next;
        }
    }

    static void deleteAll () {
        ListNode curNode = head;
        while (curNode != null) {    //不是null就一定有next
            ListNode curNext = curNode.next;    //这一行代码的位置真的很有学问
            curNode.prev = null;
            curNode.next = null;
            curNode = curNext;
        }
        head = null;
        last = head;

//        if (head == null || head == last) {
//            head = null;
//            last = head;
//            return;
//        }
//        ListNode curNode = head.next;
//        while (curNode != last && curNode.next != last) {
//            curNode.next.prev = null;
//            curNode = curNode.next;
//        }
//        head = null;
//        last = head;
    }

    static void delete (int data) {
        //没有元素直接退出
        if (head == null) {
            return;
        }

        //第一个就是特殊处理
        if (head.val == data) {
            if (last == head) {
                last = null;
                head = null;
            } else {
                head.next.prev = null;
                head = head.next;
            }
        }

        if (last.val == data) {
            if (last == head) {
                last = null;
                head = null;
            } else {
                last.prev.next = null;
                last = last.prev;
            }
        }


        //从第二个开始比较
        ListNode preNode = head;
        ListNode curNode = head.next;
        while (curNode.next != null) {
            if (curNode.val == data) {
                preNode.next = curNode.next;
                curNode.next.prev = preNode;
            }
            curNode = curNode.next;
            preNode = curNode.prev;
        }

    }

    static boolean contains (int data) {
        ListNode tmpNode = head;
        while (tmpNode != null) {
            if (data == tmpNode.val) {
                return true;
            }
        }
        return false;
    }

}

//class Ts {
//    public static void main(String[] args) {
//        LinkedList.addLast(5);
//        LinkedList.addLast(6);
//        LinkedList.addLast(7);
//        LinkedList.addFirst(4);
//        LinkedList.addFirst(3);
//        LinkedList.addFirst(2);
//        LinkedList.addFirst(1);
////        LinkedList.addIndex(8,8);
//        LinkedList.display(LinkedList.head);
//        System.out.println();
//        LinkedList.delete(0);
//        LinkedList.delete(7);
//        LinkedList.display(LinkedList.head);
//    }
//}

class Test {
    public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(1);
        arrayList.add(2);
        arrayList.add(3);
        LinkedList<Integer> linkedList = new LinkedList(arrayList);

        ListIterator<Integer> iterator = linkedList.listIterator(linkedList.size());
        while (iterator.hasPrevious()) {
            System.out.print(iterator.previous() + " ");
        }
        System.out.println();
        System.out.println("=========");
        ListIterator<Integer> iterator1 = linkedList.listIterator();
        while (iterator1.hasNext()) {
            System.out.print(iterator1.next() + " ");
        }
    }
}